Pada awal abad ke-19, pemerintahan Belanda terbatas pada pulau Jawa dan pesisir pantai selatan Sumatera, Maluku, dan pulau-pulau lain. Pemerintahan Belanda hanya menjadi mantap di kepulauan Hindia Timur Belanda menjelang tahun 1900, dan anggota tentera Afrika memainkan peranan dalam pengembangan pemerintahan ini. Kompeni-kompeni Afrika bertempur bersama-sama anggota tentera KNIL berbangsa Eropah dalam kempen-kempen Belanda di Sumatera, Kalimantan, Sulawesi, Bali, Timor, dan Aceh.[16]

Antara kontinjen bukan Eropah dalam Ekspedisi Aceh Kedua pada tahun 1873, terdapat dua kompeni yang dianggotai orang Afrika Barat, iaitu Haf Kanan (Belanda: Rechter Halve) ke-3 dan ke-4 daripada Batalion Infantri Kedua di bawah pimpinan Leftenan Kolonel K. van der Heijden. Dari segi kekuatan, bilangannya kecil sahaja, hanya kira-kira 230 orang daripada keseluruhan tenaga seramai 13,000 orang. Namun, anggota-anggota ini menyertai angkatan KNIL dengan reputasi yang sangat baik; tambah lagi, mereka tahan dengan keadaan tempatan. Mereka menerima gaji yang lebih tinggi daripada anggota peribumi dan berkongsi kandang kuda dengan tentera Eropah. Kedua-dua kompeni Afrika tersebut berkhidmat di bawah Mejar M.A.E. Phaff.[17]

Sementara itu, orang Aceh memulakan ekspedisi hukuman terhadap kampung-kampung yang telah bekerjasama dengan Belanda. Tentera Afrika dikerahkan untuk melindungi daerah-daerah Meuraksa dan Lampaseh di Aceh, dan pada 26 Julai 1874 juga Surian— ini membolehkan orang awam untuk bergerak melalui sungai Aceh dan melintas laluan dari pantai ke Kuta Raja dengan aman.[18] Sejak menakluk Surian pada 26 Julai 1874, orang Afrika juga bertugas mengeluarkan kad pelawat untuk sesiapa warga Aceh yang ingin berkunjung ke sana. Dalam kempen ini, seorang penembak Afrika, T. Tak, dianugerahi pingat Kesatria Kelas 4, Darjah Tentera Willem, Sarjan Afrika J. Noudjedij dan para soldadu Afrika J. Hat, W. Muil, dan W. Bamberg dianugerahi Pingat Gangsa Keberanian dan Kesetiaan, manakala W. Zwol dan T. Zaal menerima sebutan khas.[19] Bilangan mereka kini menurun daripada 230 kepada 116 orang oleh sebab pusing ganti dan kekurangan rekrut baru. Keadaan ini kekal sehinggalah kekuatan Kompeni Haf Kanan ke-3 dan ke-4 Batalion Infantri Kedua dipulihkan dengan tambahan orang-orang Eropah.

Pada 8 November 1875, Kolonel J.L.J.H. Pel kembali ke Aceh sebagai Mejar Jeneral dan Panglima Tertinggi. Pada 9 November, beliau mengambil alih kuasa daripada Kolonel Wiggers van Kerchem, yang meninggalkan Aceh pada 10 November.[20] Semasa Perang Aceh, di bawah pimpinan Mejar Jeneral Pel, bilangan anggota tentera Afrika telah mengurang kepada kira-kira 176 orang.[21] Dengan kebenaran pemerintahan Hindia, Pel membuat dua orang pegawai tentera British-India, iaitu Kapten A.P. Palmer dan Kapten W.S.A. Lockhart, sebagai pemerhati tentera bagi sebahagian operasi peperangan.[22] Palmer kemudian menulis dalam laporannya bahawa tentera Afrika setakat itu adalah yang terbaik dalam kalangan anggota tentera Tentera Hindia. Palmer tidak amat menghargai penembak-penembak Eropah dan Jawa yang kurang terlatih, tetapi mengambil maklum bahawa orang Aceh mempunyai penghormatan tinggi terhadap orang Afrika Barat. Untuk mengisi kompeni Afrika Barat, percubaan masih dilakukan dan cara-cara lain dicari untuk memenuhi kekurangan tentera Afrika tersebut, tetapi usaha itu runtuh kerana bantahan British yang merasakan usaha itu sebenarnya sebuah penyamaran yang mudah untuk satu tindakan perhambaan.